package org.hfy.collections;


import dnl.utils.text.table.TextTable;
import org.hfy.Constants;
import org.hfy.collections.helper.*;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Description:
 * @Author: Takagi
 * @date: 2023/5/6
 */
public class StdLRAutomaton extends LRAutomaton {
    // 是否为 LALR 自动机
    public boolean LALR = false;

    /*
     * @Author Takagi
     * @Description: 获取搜索符
     * @date: 2023/5/13
     * @param string
     * @return * @return SymbolString
     **/
    public SymbolString getSearchSymbols(SymbolString string) {
        int idx = string.indexOf(new SearchSymbolSeparator());
        if (idx != -1) {
            return string.subString(idx + 1, string.size());
        }
        return null;
    }

    /*
     * @Author Takagi
     * @Description: 判断非终结符是否只能推导出空串
     * @date: 2023/5/13
     * @param symbol
     * @return * @return boolean
     **/
    boolean onlyDeriveEpsilon(Symbol symbol) {
        int cnt = 0;
        boolean flag = false;
        for (Production production : this.productions) {
            if (production.left == symbol) {
                ++cnt;
                if (Constants.isEpsilon(production.right.getFirstSymbol())) flag = true;
            }
        }
        return cnt == 1 && flag;
    }

    /*
     * @Author Takagi
     * @Description: 求解搜索符
     * @date: 2023/5/13
     * @param right
     * @param itemNextSymbol
     * @return * @return SymbolString
     **/
    public SymbolString solveSearchSymbols(SymbolString right, Symbol itemNextSymbol) {
        // S -> · A B , β
        // itemNextSymbol : A
        // next : B
        // return First( Bβ )
        SymbolString right_ = right.subString(right.indexOf(new LR1Item()), right.size());
        Symbol next = right_.getNext(itemNextSymbol);
        // 若 B 为空，则继承搜索符 β
        if (next.content.equals(Constants.SEARCH_SYMBOL_SEPARATOR) || this.onlyDeriveEpsilon(next)) {
            return this.getSearchSymbols(right_);
        } else {
            // 否则为 First(B)
            SymbolString string = new SymbolString();
            NonTerminator nonTerminator = this.getNonTerminatorByName(next);
            if (nonTerminator != null) {
                string.extendSymbols(nonTerminator.First);
            } else {
                string.addSymbol(next);
            }
            return string;
        }
    }

    /*
     * @Author Takagi
     * @Description: 求项目集闭包
     * @date: 2023/5/13
     * @param itemSet
     * @return * @return Set<Production>
     **/
    public Set<Production> getItemSetClosure(ItemSet itemSet) {
        Set<Production> coreItemSet = itemSet.coreItemSet;
        Set<Production> result = new HashSet<>();
        Set<Symbol> visited = new HashSet<>();
        // 需要求解闭包的产生式
        Queue<Production> need = new LinkedList<>(coreItemSet);

        while (need.size() > 0) {
            // S -> · AB, C
            Production item = need.poll();
            Symbol symbol = item.getItemNextSymbol();  // A
            if (symbol.content.equals(Constants.SEARCH_SYMBOL_SEPARATOR)) continue;
            SymbolString searchSymbols = this.solveSearchSymbols(item.right, symbol); // First(BC)
            NonTerminator nonTerminator = this.getNonTerminatorByName(symbol);  // A

            if (nonTerminator != null) {
                for (SymbolString equal : nonTerminator.equalList) {
                    // A -> β γ
                    // string : · β γ , C
                    SymbolString string = new SymbolString();
                    string.addSymbol(Constants.LR1_ITEM);
                    string.extendSymbols(equal);
                    string.addSymbol(Constants.SEARCH_SYMBOL_SEPARATOR);
                    string.extendSymbols(searchSymbols);

                    // A -> · β γ , C
                    Production production = new Production(symbol, string);
                    result.add(production);

                    Symbol first = equal.getFirstSymbol(); // β
                    // 若 β 是非终结符，并且没有求过闭包，加入待求闭包队列
                    // 由 β 推出的产生式，搜索符由 First(γC) 决定
                    if (Constants.isNonTerminator(first) && !visited.contains(first)) {
                        visited.add(first);
                        need.add(production);
                    }
                }
            }
        }
        return result;
    }

    /*
     * @Author Takagi
     * @Description: 获取初始项目集
     * @date: 2023/4/25
     * @param
     * @return * @return ItemSet
     **/
    @Override
    public ItemSet getInitialItemSet() {
        // 项目集合：核心项目、非核心项目
        // 每个 核心/非核心 项目用产生式表示
        ItemSet itemSet = new ItemSet();

        // S' -> S
        Production production = new Production();
        production.left = this.extendGrammarProduction.left;
        production.right = new SymbolString();
        production.right.addSymbol(new LR1Item());
        production.right.extendSymbols(this.extendGrammarProduction.right);
        production.right.addSymbol(new SearchSymbolSeparator());
        production.right.addSymbol(new Symbol(Constants.EOF));


        // 将 S' -> S 加入核心项目
        itemSet.addCoreItem(production);

        // 非核心项目是核心项目的闭包
        itemSet.nonCoreItemSet = getItemSetClosure(itemSet);

        return itemSet;
    }


    /*
     * @Author Takagi
     * @Description: 获取归约项目的输入（遇到什么符号进行归约）
     *              即项目的所有搜索符
     * @date: 2023/5/13
     * @param itemSet
     * @return * @return SymbolString
     **/
    public SymbolString getReduceInputs(ItemSet itemSet) {
        return getSearchSymbols(itemSet.getFirstCoreItem().right);
    }


    /*
     * @Author Takagi
     * @Description: 处理状态转移
     * @date: 2023/5/13
     * @param name
     * @param itemSet
     * @param itemSetFamily
     * @return * @return State
     **/
    public State solveState(int name, ItemSet itemSet, List<ItemSet> itemSetFamily) {
        Set<Symbol> inputs = itemSet.getInputSymbols();
        State state = new State();
        state.setName(name);
        int offset = 1;
        // 接受状态
        if (itemSet.isAcceptState(extendGrammarProduction.left)) {
            state.setAcceptAction(new Symbol(Constants.EOF));
        } else if (itemSet.isReducedState()) {
            // 归约状态
            Production item = itemSet.getFirstCoreItem();
            for (Symbol input : getReduceInputs(itemSet).getSymbolList()) {
                state.setReduceAction(input, indexOfProduction(item.getProductionIgnoreItem()) + offset, item);
            }
        } else {
            for (Symbol input : inputs) {
                // I0  move a 之后，由于合并了同心集，少了 $
                ItemSet next = move(itemSet, input);
                int j = indexOfItemSet(itemSetFamily, next);
                // 输入非终结符
                if (Constants.isNonTerminator(input)) {
                    state.setGoto(input, j);
                } else {
                    // 输入终结符
                    if (next.isAcceptState(this.extendGrammarProduction.left)) {
                        state.setAcceptAction(input);
                    } else {
                        state.setShiftAction(input, j);
                    }
                }
            }
        }
        return state;
    }
}
